package com.lw.leetcode.dp.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * Created with IntelliJ IDEA.
 * dp
 * b
 * LCP 64. 二叉树灯饰
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/9 10:05
 */
public class CloseLampInTree {

    public static void main(String[] args) {
        CloseLampInTree test = new CloseLampInTree();

        TreeNode node = TreeNode.getInstance21();

        int i = test.closeLampInTree(node);
        System.out.println(i);
    }

    public int closeLampInTree(TreeNode root) {
        return find(root).c;
    }

    private Node find(TreeNode node) {
        Node no = new Node();
        if (node == null) {
            return no;
        }
        Node left = find(node.left);
        Node right = find(node.right);
        if (node.val == 1) {
            no.a = Math.min(Math.min(left.a + right.a, left.c + right.c + 2), Math.min(left.b + right.b + 2, left.d + right.d + 2));
            no.b = Math.min(Math.min(left.a + right.a + 2, left.c + right.c), Math.min(left.b + right.b + 2, left.d + right.d + 2));
            no.c = Math.min(Math.min(left.a + right.a + 1, left.c + right.c + 1), Math.min(left.b + right.b + 1, left.d + right.d + 3));
            no.d = Math.min(Math.min(left.a + right.a + 1, left.c + right.c + 1), Math.min(left.b + right.b + 3, left.d + right.d + 1));
        } else {
            no.a = Math.min(Math.min(left.a + right.a + 1, left.c + right.c + 1), Math.min(left.b + right.b + 3, left.d + right.d + 1));
            no.b = Math.min(Math.min(left.a + right.a + 1, left.c + right.c + 1), Math.min(left.b + right.b + 1, left.d + right.d + 3));
            no.c = Math.min(Math.min(left.a + right.a + 2, left.c + right.c), Math.min(left.b + right.b + 2, left.d + right.d + 2));
            no.d = Math.min(Math.min(left.a + right.a, left.c + right.c + 2), Math.min(left.b + right.b + 2, left.d + right.d + 2));
        }
        return no;
    }

    private static class Node {
        private int a;
        private int b;
        private int c;
        private int d;
    }

}
